package com.kehao.leetcode.middle.design;

import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

//二叉树的序列化与反序列化

public class Codec {
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuffer sb = new StringBuffer();
        addToString(root,sb);
        return new String(sb);
    }

    private void addToString(TreeNode root, StringBuffer sb) {
        if(root==null){
            sb.append('#');
        }else {
            sb.append(root.val);
            sb.append(',');
            addToString(root.left,sb);
            sb.append(',');
            addToString(root.right,sb);
        }
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] split = data.split(",");
        List<String> list = new LinkedList();
        for (int i = 0; i < split.length; i++) {
            list.add(split[i]);
        }
        return generateTree(list);
    }

    private TreeNode generateTree(List<String> list) {
        if(list.size()==0) return null;
        String remove = list.remove(0);
        if(remove.equals("#")) return null;
        TreeNode result = new TreeNode(Integer.parseInt(remove));
        result.left = generateTree(list);
        result.right = generateTree(list);
        return result;
    }


    @Test
    public void test01(){
        Integer[] array = {1,2,3,null,null,4,5};
        TreeNode root = buildTree(array);
        String serialize = serialize(root);
        System.out.println(serialize);
    }

    @Test
    public void test02(){
        String str = "1,2,#,#,3,4,#,#,5,#,#";
        TreeNode deserialize = deserialize(str);
        System.out.println();
    }

    private TreeNode buildTree(Integer[] array) {
        HashMap<Integer, TreeNode> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if(array[i]!=null){
                map.put(i,new TreeNode(array[i]));
            }
        }
        for (int i = 0; i < array.length; i++) {
            if(array[i]!=null){
                map.get(i).left = map.get(i*2+1);
                map.get(i).right = map.get(i*2+2);
            }
        }
        return  map.get(0);
    }
}
